class Solution {
public:
    /*
    动态规划：
    dp[i]表示：包含i位置的最长湍流子数组
    */
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        if (n == 1)
            return 1;
        if (n == 2)
            return arr[0] == arr[1] ? 1 : 2;

        vector<int> dp(n);
        if (arr[0] == arr[1])
            dp[0] = dp[1] = 1;
        else
        {
            dp[0] = 1;
            dp[1] = 2;
        }

        int ret = dp[1], flag = arr[1] - arr[0];
        for (int i = 2; i < n; ++i)
        {
            int tmp = arr[i] - arr[i - 1];
            if (tmp == 0)
                dp[i] = 1;
            else
            {
                if (flag < 0 && tmp < 0 || flag > 0 && tmp > 0 || flag == 0)
                    dp[i] = 2;
                else
                    dp[i] = dp[i - 1] + 1;
            }
            flag = tmp;
            ret = max(ret, dp[i]);
        }

        return ret;
    }
};